﻿//930. 和相同的二元子数组
//给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。
//子数组 是数组的一段连续部分。

//哈希表

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal)
    {
        int n = nums.size();
        int ans = 0;
        int sum = 0;
        unordered_map<int, int> cnt;
        for (auto& num : nums)
        {
            cnt[sum]++;
            sum += num;
            ans += cnt[sum - goal];
        }
        return ans;
    }
};

//滑动窗口

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal)
    {
        int n = nums.size();
        int ans = 0;
        int sum1 = 0, sum2 = 0;
        int left1 = 0, left2 = 0, right = 0;
        for (; right < n; right++)
        {
            sum1 += nums[right];
            //不满足条件
            while (left1 <= right && sum1 > goal)
            {
                sum1 -= nums[left1];
                left1++;
            }
            sum2 += nums[right];
            while (left2 <= right && sum2 >= goal)
            {
                sum2 -= nums[left2];
                left2++;
            }
            ans += left2 - left1;
        }
        return ans;
    }
};